package Sequence;

public class Test0115 {
    public static void main(String[] args) {
        String s = "rabbbit";
        String t = "rabbit";

        Solution0115_1 solution0115_1 = new Solution0115_1();
        int i = solution0115_1.numDistinct(s, t);
        System.out.println(i);
    }
}

class Solution0115_1 {
    public int numDistinct(String s, String t) {
        char[] charArray1 = s.toCharArray();
        char[] charArray2 = t.toCharArray();

        int length2 = t.length();

        int[] dp1 =new int[length2 + 1];
        int[] dp2 =new int[length2 + 1];
        dp2[0]=1;
        dp1[0] = 1;


        for (char c1 : charArray1) {
            for (int i = 0; i < length2; i++) {
                dp2[i + 1] = dp1[i+1];

                char c2 = charArray2[i];
                if (c1 == c2) {
                    dp2[i + 1] += dp1[i];
                }
            }

            int[] temp = dp1;
            dp1 = dp2;
            dp2 = temp;
        }

        return dp1[length2];
    }
}
